package leetcode.string;

import datastructure.map.HashMap;

import java.util.Arrays;

/**
 * @Description: https://leetcode.cn/problems/longest-substring-without-repeating-characters/
 * @Author Ammar
 * @Create 2023/7/13 19:24
 */
public class _3_无重复字符的最长子串 {
    public int lengthOfLongestSubstring(String s) {
        if (s == null) return 0;
        char[] chars = s.toCharArray();
        if (chars.length == 0) return 0;
        HashMap<Character, Integer> prevIndex = new HashMap<>();
        // 字符上一次出现的索引
        prevIndex.put(chars[0], 0);
        // 以 i - 1 位置字符结尾的最长不重复字符串的开始索引
        int li = 0;
        int max = 1;
        for (int i = 1; i < chars.length; i++) {
            Integer pi = prevIndex.get(chars[i]);
            if (pi != null && pi >= li) {
                li = pi + 1;
            }

            prevIndex.put(chars[i], i);
            max = Math.max(max, i - li + 1);
        }
        return max;
    }

    public int lengthOfLongestSubstring2(String s) {
        if (s == null) return 0;
        char[] chars = s.toCharArray();
        if (chars.length == 0) return 0;
        int[] prevIndex = new int[128];
        Arrays.fill(prevIndex, -1);
        // 字符上一次出现的索引
        prevIndex[chars[0]] = 0;
        // 以 i - 1 位置字符结尾的最长不重复字符串的开始索引
        int li = 0;
        int max = 1;
        for (int i = 1; i < chars.length; i++) {
            int pi = prevIndex[chars[i]];
            if (pi != -1 && pi >= li) {
                li = pi + 1;
            }

            prevIndex[chars[i]] = i;
            max = Math.max(max, i - li + 1);
        }
        return max;
    }
}
